package practice1_100;

public class Practice312 {
    public int maxCoins(int[] nums) {
        int[][] res=new int[nums.length+2][nums.length+2];
        int[] val=new int[nums.length+2];
        for (int i = 0; i < nums.length; i++) {
            val[i+1]=nums[i];
        }
        int n=nums.length;
        //i left
        //j right
        for (int i = n-1; i >=0 ; i--) {
            for (int j = i+2; j <n+1 ; j++) {
                for (int k = i+1; k < j; k++) {
                    int sum=val[i]*val[k]*val[j];
                    sum+=res[i][k]+res[k][j];
                    res[i][j]=Math.max(res[i][j],sum);
                }
            }
        }
        return res[0][nums.length+1];
    }

    public static void main(String[] args) {
        new Practice312().maxCoins(new int[]{2,5,6,3,6,2,6,8,4,10});
    }
}
